package com.tianyuan.test3;

/**
 * 二叉树的后序遍历
 *
 * @date 2025/10/17 10:22
 * 给定一个二叉树，返回他的后序遍历的序列。
 * 后序遍历是值按照左节点->右节点->根节点的顺序的遍历。
 * 数据范围：二叉树的节点数量满足1≤n≤100，二叉树节点的值满足1≤val≤100，树的各节点的值各不相同
 * 输入：{1,#,2,3} 返回值：[3,2,1]
 * 输入：{1} 返回值：[1]
 */
import java.util.*;

public class Solution {
    /**
     * 主方法：对外提供的后序遍历入口，返回int数组格式的遍历结果
     * 方法名、参数、返回值均由题目指定，不可修改
     * @param root 二叉树的根节点（若树为空，root为null）
     * @return 按后序顺序排列的节点值数组
     */
    public int[] postorderTraversal (TreeNode root) {
        // 1.初始化动态列表：用于临时存储遍历结果
        // 选择ArrayList是因为其支持动态添加元素，无需提前确定树的节点数量
        ArrayList<Integer> resultList = new ArrayList<>();
        // 2.调用递归函数：传入结果列表和根节点，开始后序遍历
        // 递归会自动按“左→右→根”顺序将节点值存入resultList
        process(resultList, root);
        // 3.结果格式转换：将ArrayList（动态列表）转为int[]（数组）
        // 题目要求返回int数组，因此需要这一步转换
        return listToArray(resultList);
    }

    /**
     * 辅助递归方法：实现后序遍历的核心逻辑
     * 作用：按“左子树→右子树→根节点”顺序遍历，将节点值存入结果列表
     * @param resultList 存储遍历结果的动态列表（由主方法传入，递归中持续添加值）
     * @param root 当前正在遍历的节点（递归中会不断传入子节点）
     */
    public void process(ArrayList<Integer> resultList, TreeNode root) {
        // 递归终止条件：若当前节点为null（空节点），直接返回上一层,避免递归无限循环
        if (root == null) {
            return;
        }
        // 第一步：递归遍历当前节点的左子树（左）
        // 先深入左子树的最深处，直到遇到null节点才返回
        process(resultList, root.left);
        // 第二步：递归遍历当前节点的右子树（右）
        // 左子树遍历完后，再深入右子树的最深处
        process(resultList, root.right);
        // 第三步：访问当前节点（根），将节点值加入结果列表
        // 只有左、右子树都遍历完，才会处理当前节点，这是后序遍历的核心标识
        resultList.add(root.val);
    }

    /**
     * 工具方法：将ArrayList<Integer>转换为int[]（数组）
     * 因为ArrayList存储的是Integer包装类，题目要求返回int基本类型数组，需手动转换
     * @param resultList 存储遍历结果的动态列表
     * @return 转换后的int数组
     */
    public int[] listToArray(ArrayList<Integer> resultList) {
        // 1.创建与列表长度相同的int数组（避免数组下标越界）
        int[] resultArray = new int[resultList.size()];
        // 2.循环遍历列表，将每个Integer值拆箱为int，存入数组对应位置
        for (int i = 0; i < resultArray.length; i++) {
            resultArray[i] = resultList.get(i);
        }
        // 3.返回转换后的数组
        return resultArray;
    }









    /**
     * 辅助方法：将字符串格式的二叉树表示转换为TreeNode对象
     * 输入格式示例：{1,#,2,3} 表示根节点为1，左子树为空，右子树为2，2的左子树为3
     * #表示空节点
     */
    private static TreeNode buildTreeFromString(String input) {
        // 处理空树或无效输入
        if (input == null || input.trim().isEmpty() || input.trim().equals("{}")) {
            return null;
        }
        // 去除首尾的{}，按逗号分割节点值
        String[] nodes = input.trim().substring(1, input.length() - 1).split(",");
        // 根节点
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0].trim()));
        // 用队列辅助构建二叉树（层序遍历方式）
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int index = 1; // 当前处理的节点索引

        while (!queue.isEmpty() && index < nodes.length) {
            TreeNode current = queue.poll();
            // 处理左子节点
            if (index < nodes.length) {
                String leftVal = nodes[index].trim();
                if (!leftVal.equals("#")) { // 非空节点
                    current.left = new TreeNode(Integer.parseInt(leftVal));
                    queue.offer(current.left);
                }
                index++;
            }
            // 处理右子节点
            if (index < nodes.length) {
                String rightVal = nodes[index].trim();
                if (!rightVal.equals("#")) { // 非空节点
                    current.right = new TreeNode(Integer.parseInt(rightVal));
                    queue.offer(current.right);
                }
                index++;
            }
        }
        return root;
    }
    public static void main(String[] args) {
        Solution solution = new Solution();

        // 测试用例1: 输入{1,#,2,3}，预期输出[3,2,1]
        String input1 = "{1,#,2,3}";
        TreeNode root1 = buildTreeFromString(input1);
        int[] result1 = solution.postorderTraversal(root1);
        System.out.println("测试用例1: " + Arrays.toString(result1));

        // 测试用例2: 输入{1}，预期输出[1]
        String input2 = "{1}";
        TreeNode root2 = buildTreeFromString(input2);
        int[] result2 = solution.postorderTraversal(root2);
        System.out.println("测试用例2: " + Arrays.toString(result2));
    }
}